package Leetcode;

import java.util.*;

public class problem17 {

    public List<String> letterCombinations(String digits){
        List<String> sList = new ArrayList<>();
        if(digits == null || digits.length() == 0){
            return sList;
        }

        Map<Character,List<String>> maps = new HashMap<>();

        maps.put('2', Arrays.asList("a", "b", "c"));
        maps.put('3', Arrays.asList("d", "e", "f"));
        maps.put('4', Arrays.asList("g", "h", "i"));
        maps.put('5', Arrays.asList("j", "k", "l"));
        maps.put('6', Arrays.asList("m", "n", "o"));
        maps.put('7', Arrays.asList("p", "q", "r","s"));
        maps.put('8', Arrays.asList("t", "u", "v"));
        maps.put('9', Arrays.asList("w", "x", "y","z"));

        if(digits.length() == 1){
            return maps.get(digits.charAt(0));
        }

        char[] arr = digits.toCharArray();

        sList.addAll(maps.get(arr[0]));

        for(int i = 1;i < arr.length;i++){
            List<String> temp = new ArrayList<>();
            temp = unionList(sList,maps.get(arr[i]));
            sList.clear();
            sList.addAll(temp);
        }
        return sList;
    }

    public List<String> unionList(List<String> sList, List<String> rList){
        List<String> temp = new ArrayList<>();
        for (String a:sList) {
            for (String b:rList) {
                temp.add((a+b));
            }
        }
        return temp;
    }

    public List<String> letterCombinations2(String digits) {
        List<String> list = new ArrayList<>();
        if(digits==null||digits.length()==0) return list;
        char[][] table = {{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},
                {'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
        dfs(digits,0,list,table,"");
        return list;
    }
    private void dfs(String digits,int i,List<String> list,char[][] table,String ans){
        if(i==digits.length()){
            list.add(ans);
            return;
        }
        int num = digits.charAt(i)-'2';
        for(int j=0;j<table[num].length;j++){
            dfs(digits,i+1,list,table,ans+table[num][j]);
        }
    }

    public static void main(String[] args) {
        problem17 p = new problem17();
        p.letterCombinations2("23");
    }

}
